package Algorithm.Tree;

/**
 * @Author cj
 * @Date 2022/1/16 16:28
 */
public class minDepth {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    public static int minDepth1(Node head) {
        if (head == null) {
            return 0;
        }
        // 遍历
        return preOrderRecur(head, 1);
    }

    private static int preOrderRecur(Node root, int depth) {
        if (root == null) {
            return depth;
        }
        if (root.left == null && root.right == null) {
            return depth;
        }
        int ans = Integer.MAX_VALUE;
        if (root.left != null) { // 返回左子树最小深度
            ans = Math.min(preOrderRecur(root.left, depth + 1), ans);
        }
        if (root.right != null) { // 返回右子树最小深度
            ans = Math.min(preOrderRecur(root.right, depth + 1), ans);
        }
        // 返回左右子树最小深度
        return ans;
    }

    // 莫里斯遍历，空间O(1)
    public static int minDepth2(Node head) {
        if (head == null) {
            return 0;
        }
        int level = 0, minLevel = Integer.MAX_VALUE;
        Node mostRight = null, cur = head;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) { // 当前cur有左子树，能到达两次
                // cur左子树上右边界节点个数
                int leftTreeRightSize = 1;
                // 找到最右节点
                while (mostRight.right != null && mostRight.right != cur) {
                    leftTreeRightSize++;
                    mostRight = mostRight.right;
                }
                // 此时mostRight已指向最右节点
                if (mostRight.right == cur) {
                    // 第二次到达cur，下一个节点level=level-leftTreeRightSize,
                    // 此时检查是否是叶子结点
                    if (mostRight.left == null) {
                        minLevel = Math.min(level, minLevel);
                    }
                    level -= leftTreeRightSize;
                    mostRight.right = null;
                } else { // mostRight.right指向null
                    // 第一次到达cur，下一个节点level值+1
                    level++;
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
            } else { // 下一个要遍历右子树，深度加1
                level++;
            }
            // mostRight.right指向head或head没有左子树
            cur = cur.right;
        }
        // 最后检查整棵树最右节点是否是叶节点
        int finalRight = 1;
        cur = head;
        while (cur.right != null) {
            finalRight++;
            cur = cur.right;
        }
        if (cur.left == null) { // 是叶子结点
            minLevel = Math.min(finalRight, minLevel);
        }
        return minLevel;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.right = new Node(2);
        head.right.left = new Node(3);
        head.right.left.left = new Node(4);
        head.right.left.right = new Node(5);
        System.out.println(minDepth1(head));
    }

}
